#include <iostream>
#include <BinaryTree.hpp>
#include <vector>
#include <stack>

using namespace std;

class Solution
{
public:
    bool dfs(TreeNode *node, vector<TreeNode *> &v, TreeNode *p)
    {
        if (node == nullptr)
            return false;
        v.push_back(node);
        if (node == p)
        {
            return true;
        }
        else
        {
            if (dfs(node->left, v, p))
                return true;
            if (dfs(node->right, v, p))
                return true;
            v.pop_back();
            return false;
        }
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        vector<TreeNode *> pq, qq;
        dfs(root, pq, p);
        pq.push_back(nullptr);
        dfs(root, qq, q);
        qq.push_back(nullptr);
        for (int i = 0; i < pq.size() - 1; i++)
        {
            cout << "," << pq[i]->val;
        }
        cout << '\n';
        for (int i = 0; i < qq.size() - 1; i++)
        {
            cout << "," << qq[i]->val;
        }
        cout << '\n';
        for (int i = 0;; i++)
        {
            if (pq[i] != qq[i])
            {
                return pq[i - 1];
            }
            cout << "," << qq[i]->val;
        }
    }
};

int main()
{
    cout << "Code236" << endl;
    Solution s;
    TreeNode *n1 = new TreeNode(1);
    TreeNode *n2 = new TreeNode(2, nullptr, n1);
    TreeNode *root = new TreeNode(56, n1, n2);
    cout << s.lowestCommonAncestor(n2, n1, n2)->val;
    return 0;
}